package com.breeze.leetcode

/**
 * https://leetcode-cn.com/problems/search-insert-position/
 * 35. 搜索插入位置
 * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 * 你可以假设数组中无重复元素。
 */
class Solution {
    /**
     * 二分查找方法
     */
    fun searchInsert(nums: IntArray, target: Int): Int {
        var right = nums.size - 1
        var left = 0

        while (left < right) {
            val mid = (right + left) / 2
            if (target > nums[mid]) { // 更新左边界
                left = mid + 1
            } else if (target < nums[mid]) { // 更新右边界
                right = mid - 1
            } else {
                return mid // 找到相等则返回
            }
        }
        // 当left和right相等时，且仍然该位置的值与target不相等，如果target较大，则下标+1，否则依然用该值
        return if (target > nums[left]) left + 1 else left
    }
}

fun main() {
    var solution = Solution()
    println(solution.searchInsert(intArrayOf(1, 3, 5, 7), 5))
    println(solution.searchInsert(intArrayOf(1, 3, 5, 7), 2))
    println(solution.searchInsert(intArrayOf(1, 3, 5, 7), 8))
    println(solution.searchInsert(intArrayOf(1, 3, 5, 7), 0))
}